1. Field
The present invention relates generally to computer graphics and, more specifically, to spatial partitioning of three-dimensional (3D) models.
2. Description
Multi-resolution geometric models (two-dimensional (2D) or 3D geometries) provide a way to efficiently change a model's resolution during run-time. A multi-resolution model is typically represented as a polygonal mesh. The polygons are usually triangles, and the mesh defines a plurality of triangles by specifying connecting vertices and edges. Multi-resolution models have several important applications, for example, reducing the processor usage for rendering objects at a distance without losing visual quality, application of key computational geometry algorithms at lower model resolutions, and streaming of models over the Internet. Multi-resolution is especially important for large models. Such models in common applications also typically have spatial partitioning data structures associated with them.
In 2D and 3D computer graphics, spatial partitioning typically includes the action of dividing up a space into smaller portions. The space may represent a scene in a world. The portions are sometimes called octants (for 3D), quadrants (for 2D), or gridlets (for 2D or 3D). Subdividing space is usually done during graphics pipeline processing to minimize future computation and to minimize the number of objects sent down the graphics pipeline. For example, if some objects in the scene are not currently visible based on the current camera position, then there is no need to further process these objects. Instead of examining each object submitted into the pipeline, when using spatial partitioning, graphics processing examines only the octants actually containing objects of the scene. For example, entire octants may be removed from further processing consideration if they are outside of the currently visible region of the scene, thus saving the time of transforming, rendering, and rasterizing the polygons of the objects contained in the non-visible octants.
Once a scene is partitioned and all objects in the scene are identified for a particular portion of the space, the results are typically stored in a spatial partitioning (SP) data structure for subsequent use by graphics processing components (such as a video game engine or an animation generator, for example). The SP data structure is usually generated after scene creation, but before scene visualization and user interaction with the scene (i.e., run-time). Typically, the SP data structure takes equal to or greater than O(n) time to construct, where n is the number of vertices in the model. During scene visualization, it may be necessary to find an object in the scene corresponding to a selected point. Given a point in 2D coordinates (e.g., x, y) or 3D coordinates (e.g., x, y, z), the SP data structure is typically traversed to find information about the object containing the point.
There are at least several existing techniques and corresponding data structures for spatial partitioning. These include uniform grids (also called regular grids), binary space partitioning (BSP) trees, octrees, and k-d trees.
A uniform grid is the simplest spatial partitioning scheme. A grid is uniformly subdivided and superimposed onto the scene. For example, if the space is 10 units by 10 units by 10 units, the space could be partitioned into 1 unit by 1 unit by 1 unit cubes (e.g., octants). Each cube may include zero or more polygons. A BSP tree is a data structure used when recursively dividing space into pairs of subspaces, each separated by a plane of arbitrary orientation and position. Partitions usually focus on polygons of static objects in the scene. Non-uniform partitioning is accomplished by positioning partition planes depending on where objects are located.
An octree is a data structure similar to a binary tree, but having a greater number of child nodes per parent node. Whereas a binary tree node typically has two child nodes (e.g., left and right children), an octree node has a specified number of child nodes (such as eight). Each node of the octree represents an octant of the scene. Each octant is sub-divided into a number of sub-octants (e.g., eight). Each node of the data structure contains pointers to the octants contained inside (e.g., a parent node points to child nodes). For 2D scenes, the tree is called a quadtree. For 3D scenes, the tree is a called an octree. Finer subdivision is performed in densely populated areas. If no objects are in an octant, then the octant is not subdivided further. An octree may be uniformly or non-uniformly subdivided, depending on the spatial partitioning algorithm used. The octree hierarchically partitions space up to a specified depth. An octree typically takes O(n log n) time to construct.
A k-d tree is a generalization of a binary tree where k is the dimension of the tree and d stands for dimension. For spatial partitioning, a k-d tree may be used to divide space. For example, each division of space denotes which side of a line (in 2D) or a plane (in 3D) an object may be on. Each time the left side of a line (or plane) or below a line (or plane) is considered, a left node of the k-d tree is examined. Each time the right side (or plane) or above a line (or plane) is considered, a right node of the k-d tree is examined. This process may be continued until a predetermined depth of the k-d tree is reached.
Regardless of which spatial partitioning scheme is used in a graphics application, a multi-resolution model's spatial partitioning must be recomputed every time a model's resolution changes during run-time. This can be a very expensive operation in a graphics processing system. A better multi-resolution representation and method of updating the representation are desired that minimize this computational expense.